500
500

Jul 20, 2013
07/13

by
James Propp

texts

######
eye 500

######
favorite 0

######
comment 0

Rotor-routing is a procedure for routing tokens through a network that can implement certain kinds of computation. These computations are inherently asynchronous (the order in which tokens are routed makes no difference) and distributed (information is spread throughout the system). It is also possible to efficiently check that a computation has been carried out correctly in less time than the computation itself required, provided one has a certificate that can itself be computed by the...

Source: http://arxiv.org/abs/1007.2389v2

121
121

Sep 21, 2013
09/13

by
James Propp

texts

######
eye 121

######
favorite 0

######
comment 0

Many of the theorems of real analysis, against the background of the ordered field axioms, are equivalent to Dedekind completeness, and hence can serve as completeness axioms for the reals. In the course of demonstrating this, the article offers a tour of some less-familiar ordered fields, provides some of the relevant history, and considers pedagogical implications.

Source: http://arxiv.org/abs/1204.4483v4

33
33

Sep 23, 2013
09/13

by
James Propp

texts

######
eye 33

######
favorite 0

######
comment 0

This article, based on joint work with Gabriel Carroll, Andy Itsara, Ian Le, Gregg Musiker, Gregory Price, Dylan Thurston, and Rui Viana, presents a combinatorial model based on perfect matchings that explains the symmetries of the numerical arrays that Conway and Coxeter dubbed frieze patterns. This matchings model is a combinatorial interpretation of Fomin and Zelevinsky's cluster algebras of type A. One can derive from the matchings model an enumerative meaning for the Markoff numbers, and...

Source: http://arxiv.org/abs/math/0511633v4

37
37

Sep 19, 2013
09/13

by
James Propp

texts

######
eye 37

######
favorite 0

######
comment 0

This document is an exposition of an assortment of open problems arising from the exact enumeration of (perfect) matchings of finite graphs. Roughly half have been solved at the time of this writing; see the document "Twenty Open Problems in Enumeration of Matchings: Progress Report" (also available from this server as math.CO/9801061). NOTE: This article has now been superseded by math.CO/9904150.

Source: http://arxiv.org/abs/math/9801060v3

39
39

Sep 18, 2013
09/13

by
James Propp

texts

######
eye 39

######
favorite 0

######
comment 0

Past efforts to classify impartial three-player combinatorial games (the theories of Li and Straffin) have made various restrictive assumptions about the rationality of one's opponents and the formation and behavior of coalitions. One may instead adopt an agnostic attitude towards such issues, and seek only to understand in what circumstances one player has a winning strategy against the combined forces of the other two. By limiting ourselves to this more modest theoretical objective, and by...

Source: http://arxiv.org/abs/math/9903153v2

47
47

Sep 21, 2013
09/13

by
James Propp

texts

######
eye 47

######
favorite 0

######
comment 0

Let T(m,n) denote the number of ways to tile an m-by-n rectangle with dominos. For any fixed m, the numbers T(m,n) satisfy a linear recurrence relation, and so may be extrapolated to negative values of n; these extrapolated values satisfy the relation T(m,-2-n) = epsilon_{m,n} T(m,n), where epsilon_{m,n} is -1 if m is congruent to 2 (mod 4) and n is odd, and is +1 is otherwise. This is equivalent to a fact demonstrated by Stanley using algebraic methods. Here I give a proof that provides, among...

Source: http://arxiv.org/abs/math/0104011v1

95
95

Jul 20, 2013
07/13

by
James Propp

texts

######
eye 95

######
favorite 0

######
comment 0

Consider the $2n$-by-$2n$ matrix $M=(m_{i,j})_{i,j=1}^{2n}$ with $m_{i,j} = 1$ for $i,j$ satisfying $|2i-2n-1|+|2j-2n-1| \leq 2n$ and $m_{i,j} = 0$ for all other $i,j$, consisting of a central diamond of 1's surrounded by 0's. When $n \geq 4$, the $\lambda$-determinant of the matrix $M$ (as introduced by Robbins and Rumsey) is not well-defined. However, if we replace the 0's by $t$'s, we get a matrix whose $\lambda$-determinant is well-defined and is a polynomial in $\lambda$ and $t$. The limit...

Source: http://arxiv.org/abs/math/0406301v1

49
49

Sep 19, 2013
09/13

by
James Propp

texts

######
eye 49

######
favorite 0

######
comment 0

I give a survey of different combinatorial forms of alternating-sign matrices, starting with the original form introduced by Mills, Robbins and Rumsey as well as corner-sum matrices, height-function matrices, three-colorings, monotone triangles, tetrahedral order ideals, square ice, gasket-and-basket tilings and full packings of loops.

Source: http://arxiv.org/abs/math/0208125v1

54
54

Sep 19, 2013
09/13

by
James Propp

texts

######
eye 54

######
favorite 0

######
comment 0

This document is a brief summary of progress that has been made on the problems posed in the document "Twenty Open Problems in Enumeration of Matchings" (also available from this server as math.CO/9801060). NOTE: This article has now been superseded by math.CO/9904150.

Source: http://arxiv.org/abs/math/9801061v3

25
25

Sep 19, 2013
09/13

by
James Propp

texts

######
eye 25

######
favorite 0

######
comment 0

Earlier researchers have studied the set of orientations of a connected finite graph $G$, and have shown that any two such orientations having the same flow-difference around all closed loops can be obtained from one another by a succession of local moves of a simple type. Here I show that the set of orientations of $G$ having the same flow-differences around all closed loops can be given the structure of a distributive lattice. The construction generalizes partial orderings that arise in the...

Source: http://arxiv.org/abs/math/0209005v1

121
121

Sep 23, 2013
09/13

by
James Propp

texts

######
eye 121

######
favorite 0

######
comment 0

This document is built around a list of thirty-two problems in enumeration of matchings, the first twenty of which were presented in a lecture at MSRI in the fall of 1996. I begin with a capsule history of the topic of enumeration of matchings. The twenty original problems, with commentary, comprise the bulk of the article. I give an account of the progress that has been made on these problems as of this writing, and include pointers to both the printed and on-line literature; roughly half of...

Source: http://arxiv.org/abs/math/9904150v2

76
76

Sep 20, 2013
09/13

by
James Propp

texts

######
eye 76

######
favorite 0

######
comment 0

Two of the pillars of combinatorics are the notion of choosing an arbitrary subset of a set with $n$ elements (which can be done in $2^n$ ways), and the notion of choosing a $k$-element subset of a set with $n$ elements (which can be done in $n \choose k$ ways). In this article I sketch the beginnings of a theory that would import these notions into the category of hedral sets in the sense of Morelli and the category of polyhedral sets in the sense of Schanuel. Both of these theories can be...

Source: http://arxiv.org/abs/math/0204009v3

36
36

Sep 21, 2013
09/13

by
James Propp

texts

######
eye 36

######
favorite 0

######
comment 0

Schanuel has pointed out that there are mathematically interesting categories whose relationship to the ring of integers is analogous to the relationship between the category of finite sets and the semi-ring of non-negative integers. Such categories are inherently geometrical or topological, in that the mapping to the ring of integers is a variant of Euler characteristic. In these notes, I sketch some ideas that might be used in further development of a theory along lines suggested by Schanuel.

Source: http://arxiv.org/abs/math/0203289v2

39
39

Sep 22, 2013
09/13

by
James Propp

texts

######
eye 39

######
favorite 0

######
comment 0

The problem of counting tilings of a plane region using specified tiles can often be recast as the problem of counting (perfect) matchings of some subgraph of an Aztec diamond graph A_n, or more generally calculating the sum of the weights of all the matchings, where the weight of a matching is equal to the product of the (pre-assigned) weights of the constituent edges (assumed to be non-negative). This article presents efficient algorithms that work in this context to solve three problems:...

Source: http://arxiv.org/abs/math/0111034v2

30
30

Sep 19, 2013
09/13

by
James Propp

texts

######
eye 30

######
favorite 0

######
comment 0

This survey article describes a method for choosing uniformly at random from any finite set whose objects can be viewed as constituting a distributive lattice. The method is based on ideas of the author and David Wilson for using ``coupling from the past'' to remove initialization bias from Monte Carlo randomization. The article describes several applications to specific kinds of combinatorial objects such as tilings, constrained lattice paths, and alternating-sign matrices.

Source: http://arxiv.org/abs/math/9801066v1

34
34

Jul 20, 2013
07/13

by
Boris Hasselblatt; James Propp

texts

######
eye 34

######
favorite 0

######
comment 0

For projectivizations of rational maps Bellon and Viallet defined the notion of algebraic entropy using the exponential growth rate of the degrees of iterates. We want to call this notion to the attention of dynamicists by computing algebraic entropy for certain rational maps of projective spaces (Theorem 6.2) and comparing it with topological entropy (Theorem 5.1). The particular rational maps we study are monomial maps (Definition 1.2), which are closely related to toral endomorphisms....

Source: http://arxiv.org/abs/math/0604521v5

34
34

Sep 19, 2013
09/13

by
James Propp; Richard Stanley

texts

######
eye 34

######
favorite 0

######
comment 0

In this paper, we continue the study of domino-tilings of Aztec diamonds. In particular, we look at certain ways of placing ``barriers'' in the Aztec diamond, with the constraint that no domino may cross a barrier. Remarkably, the number of constrained tilings is independent of the placement of the barriers. We do not know of a combinatorial explanation of this fact; our proof uses the Jacobi-Trudi identity.

Source: http://arxiv.org/abs/math/9801067v3

33
33

Sep 21, 2013
09/13

by
Gregg Musiker; James Propp

texts

######
eye 33

######
favorite 0

######
comment 0

Fomin and Zelevinsky show that a certain two-parameter family of rational recurrence relations, here called the (b,c) family, possesses the Laurentness property: for all b,c, each term of the (b,c) sequence can be expressed as a Laurent polynomial in the two initial terms. In the case where the positive integers b,c satisfy bc 4, the recurrence is related to Kac-Moody rank 2 Lie algebras of hyperbolic type. Here we investigate the borderline cases bc=4, corresponding to Kac-Moody Lie algebras...

Source: http://arxiv.org/abs/math/0602408v5

23
23

Sep 23, 2013
09/13

by
Alexander E. Holroyd; James Propp

texts

######
eye 23

######
favorite 0

######
comment 0

The rotor walk is a derandomized version of the random walk on a graph. On successive visits to any given vertex, the walker is routed to each of the neighboring vertices in some fixed cyclic order, rather than to a random sequence of neighbors. The concept generalizes naturally to Markov chains on a countable state space. Subject to general conditions, we prove that many natural quantities associated with the rotor walk (including normalized hitting frequencies, hitting times and occupation...

Source: http://arxiv.org/abs/0904.4507v3

18
18

Sep 24, 2013
09/13

by
Henry Cohn; Robin Pemantle; James Propp

texts

######
eye 18

######
favorite 0

######
comment 0

A sink-free orientation of a finite undirected graph is a choice of orientation for each edge such that every vertex has out-degree at least 1. Bubley and Dyer (1997) use Markov Chain Monte Carlo to sample approximately from the uniform distribution on sink-free orientations in time O(m^3 log (1/epsilon)), where m is the number of edges and epsilon the degree of approximation. Huber (1998) uses coupling from the past to obtain an exact sample in time O(m^4). We present a simple randomized...

Source: http://arxiv.org/abs/math/0103189v2

30
30

Sep 18, 2013
09/13

by
Henry Cohn; Noam Elkies; James Propp

texts

######
eye 30

######
favorite 0

######
comment 0

We prove an asymptotic formula for the probability that, if one chooses a domino tiling of a large Aztec diamond at random according to the uniform distribution on such tilings, the tiling will contain a domino covering a given pair of adjacent lattice squares. This formula quantifies the effect of the diamond's boundary conditions on the behavior of typical tilings; in addition, it yields a new proof of the arctic circle theorem of Jockusch, Propp, and Shor. Our approach is to use the saddle...

Source: http://arxiv.org/abs/math/0008243v1

32
32

Sep 19, 2013
09/13

by
Henry Cohn; Michael Larsen; James Propp

texts

######
eye 32

######
favorite 0

######
comment 0

Using a calculus of variations approach, we determine the shape of a typical plane partition in a large box (i.e., a plane partition chosen at random according to the uniform distribution on all plane partitions whose solid Young diagrams fit inside the box). Equivalently, we describe the distribution of the three different orientations of lozenges in a random lozenge tiling of a large hexagon. We prove a generalization of the classical formula of MacMahon for the number of plane partitions in...

Source: http://arxiv.org/abs/math/9801059v3

22
22

Sep 18, 2013
09/13

by
Henry Cohn; Richard Kenyon; James Propp

texts

######
eye 22

######
favorite 0

######
comment 0

We formulate and prove a variational principle (in the sense of thermodynamics) for random domino tilings, or equivalently for the dimer model on a square grid. This principle states that a typical tiling of an arbitrary finite region can be described by a function that maximizes an entropy integral. We associate an entropy to every sort of local behavior domino tilings can exhibit, and prove that almost all tilings lie within epsilon (for an appropriate metric) of the unique entropy-maximizing...

Source: http://arxiv.org/abs/math/0008220v3

48
48

Sep 22, 2013
09/13

by
Mireille Bousquet-Mélou; James Propp; Julian West

texts

######
eye 48

######
favorite 0

######
comment 0

In 1991, David Gale and Raphael Robinson, building on explorations carried out by Michael Somos in the 1980s, introduced a three-parameter family of rational recurrence relations, each of which (with suitable initial conditions) appeared to give rise to a sequence of integers, even though a priori the recurrence might produce non-integral rational numbers. Throughout the '90s, proofs of integrality were known only for individual special cases. In the early '00s, Sergey Fomin and Andrei...

Source: http://arxiv.org/abs/0906.3125v1

61
61

Sep 23, 2013
09/13

by
David Feldman; James Propp; Sinai Robins

texts

######
eye 61

######
favorite 0

######
comment 0

Our earlier article proved that if $n > 1$ translates of sublattices of $Z^d$ tile $Z^d$, and all the sublattices are Cartesian products of arithmetic progressions, then two of the tiles must be translates of each other. We re-prove this Theorem, this time using generating functions. We also show that for $d \geq 1$, not every finite tiling of $Z^d$ by lattices can be obtained from the trivial tiling by the process of repeatedly subdividing a tile into sub-tiles that are translates of one...

Source: http://arxiv.org/abs/1006.0472v2

46
46

Sep 23, 2013
09/13

by
Boris Hasselblatt; Zbigniew Nitecki; James Propp

texts

######
eye 46

######
favorite 0

######
comment 0

The topological entropy of a continuous self-map of a compact metric space can be defined in several distinct ways; when the space is not assumed compact, these definitions can lead to distinct invariants. The original, purely topological invariant defined by Adler et. al. is infinite if the system has at least one orbit with empty limit set. The Bowen-Dinaburg formulation (based on separated sets) is equivalent to the invariant defined by Friedland (based on a compactification of the inverse...

Source: http://arxiv.org/abs/math/0511495v1

29
29

Sep 21, 2013
09/13

by
David Feldman; James Propp; Sinai Robins

texts

######
eye 29

######
favorite 0

######
comment 0

We use Fourier methods to prove that if $n > 1$ translates of sublattices of $Z^d$ tile $Z^d$, and all the sublattices are Cartesian products of arithmetic progressions, then two of the tiles must be translates of each other. This is a multi-dimensional generalization of the Mirsky-Newman Theorem.

Source: http://arxiv.org/abs/0905.0441v2

36
36

Sep 19, 2013
09/13

by
William Jockusch; James Propp; Peter Shor

texts

######
eye 36

######
favorite 0

######
comment 0

In this article we study domino tilings of a family of finite regions called Aztec diamonds. Every such tiling determines a partition of the Aztec diamond into five sub-regions; in the four outer sub-regions, every tile lines up with nearby tiles, while in the fifth, central sub-region, differently-oriented tiles co-exist side by side. We show that when n is sufficiently large, the shape of the central sub-region becomes arbitrarily close to a perfect circle of radius n/sqrt(2) for all but a...

Source: http://arxiv.org/abs/math/9801068v1

32
32

Sep 23, 2013
09/13

by
Noam Elkies; Greg Kuperberg; Michael Larsen; James Propp

texts

######
eye 32

######
favorite 0

######
comment 0

We introduce a family of planar regions, called Aztec diamonds, and study the ways in which these regions can be tiled by dominoes. Our main result is a generating function that not only gives the number of domino tilings of the Aztec diamond of order $n$ but also provides information about the orientation of the dominoes (vertical versus horizontal) and the accessibility of one tiling from another by means of local modifications. Several proofs of the formula are given. The problem turns out...

Source: http://arxiv.org/abs/math/9201305v1

20
20

Sep 19, 2013
09/13

by
Omer Angel; Alexander E. Holroyd; James B. Martin; James Propp

texts

######
eye 20

######
favorite 0

######
comment 0

Holroyd and Propp used Hall's marriage theorem to show that, given a probability distribution pi on a finite set S, there exists an infinite sequence s_1,s_2,... in S such that for all integers k >= 1 and all s in S, the number of i in [1,k] with s_i = s differs from k pi(s) by at most 1. We prove a generalization of this result using a simple explicit algorithm. A special case of this algorithm yields an extension of Holroyd and Propp's result to the case of discrete probability...

Source: http://arxiv.org/abs/0910.1077v3

63
63

Jul 20, 2013
07/13

by
Giuliano Pezzolo Giacaglia; Lionel Levine; James Propp; Linda Zayas-Palmer

texts

######
eye 63

######
favorite 0

######
comment 0

In rotor walk on a finite directed graph, the exits from each vertex follow a prescribed periodic sequence. Here we consider the case of rotor walk where a particle starts from a designated source vertex and continues until it hits a designated target set, at which point the walk is restarted from the source. We show that the sequence of successively hit targets, which is easily seen to be eventually periodic, is in fact periodic. We show moreover that reversing the periodic patterns of all...

Source: http://arxiv.org/abs/1107.4442v2

75
75

Sep 23, 2013
09/13

by
Steven Linton; James Propp; Tom Roby; Julian West

texts

######
eye 75

######
favorite 0

######
comment 0

We consider a large family of equivalence relations on permutations in Sn that generalise those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of pattern-replacing moves of prescribed form; however, we limit our focus to patterns where two elements are transposed, subject to the constraint that a third element of a suitable type be in a suitable position....

Source: http://arxiv.org/abs/1111.3920v1

29
29

Sep 19, 2013
09/13

by
David Gale; James Propp; Scott Sutherland; Serge Troubetzkoy

texts

######
eye 29

######
favorite 0

######
comment 0

We discuss some properties of a class of cellular automata sometimes called a "generalized ant". This system is perhaps most easily understood by thinking of an ant which moves about a lattice in the plane. At each vertex (or "cell"), the ant turns right or left, depending on the the state of the cell, and then changes the state of the cell according to certain prescribed rule strings. (This system has been the subject of several Mathematical Entertainments columns in the...

Source: http://arxiv.org/abs/math/9501233v1

48
48

Sep 23, 2013
09/13

by
Alexander E. Holroyd; Lionel Levine; Karola Meszaros; Yuval Peres; James Propp; David B. Wilson

texts

######
eye 48

######
favorite 0

######
comment 0

We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several intriguing open problems.

Source: http://arxiv.org/abs/0801.3306v4